package binary_tree.Leetcode;

import sun.font.CreatedFontTracker;

/**
 * 根据前序和中序遍历结构构建二叉树
 * 1.不断从前序结果集中取出元素，此元素作为当前树的根节点
 * 2.拿着根节点去中序遍历中查找该节点值所处的位置，数组左侧就是左子树，右侧就是右子树
 * 3.递归上述流程，知道前序遍历结果全部遍历结束
 */
public class Num105_ConstructTreePreAndIn {
    private int Index=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildHelper( preorder,inorder,0,preorder.length-1);
    }
    private TreeNode buildHelper(int[] preorder,int[] inorder,int left,int right){
        //边界条件
        if(left>right){
            return null;
        }
        if(Index==preorder.length){
            //此时说明元素已经全部处理完毕
            return null;
        }
        //创建根节点
        TreeNode root=new TreeNode(preorder[Index]);
        Index++;
        int pos=find(root.val,inorder);
        root.left=buildHelper(preorder,inorder,left,pos-1);
        root.right=buildHelper(preorder,inorder,pos+1,right);
        return root;
    }

    private int find(int val, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i]==val){
                return i;
            }
        }
        return -1;
    }

}
